package com.lun.medium;

import java.util.ArrayList;
import java.util.List;

public class Permutations {

	// 方法一：回溯算法
	public List<List<Integer>> permute(int[] nums) {
		List<List<Integer>> results = new ArrayList<>();
		List<Integer> path = new ArrayList<>();
		boolean[] used = new boolean[nums.length];
		backtracking(path, nums, used, results);
		return results;
	}

	private void backtracking(List<Integer> path, int[] nums, boolean[] used, List<List<Integer>> results) {
		if (path.size() == nums.length) {
			results.add(new ArrayList<>(path));
			return;
		}

		for (int i = 0; i < nums.length; i++) {
			if (used[i])
				continue;

			used[i] = true;
			path.add(nums[i]);
			backtracking(path, nums, used, results);
			path.remove(path.size() - 1);
			used[i] = false;
		}
	}

	
	// 方法二：回溯算法2
	public List<List<Integer>> permute2(int[] nums) {
		List<List<Integer>> results = new ArrayList<>();
		List<Integer> path = new ArrayList<>();
		backtracking2(path, 0, nums, results);
		return results;
	}

	private void backtracking2(List<Integer> path, int startIndex, //
			int[] array, List<List<Integer>> results) {

		if (startIndex == array.length) {
			results.add(new ArrayList<>(path));
			return;
		}

		for (int i = startIndex; i < array.length; i++) {
			swap(array, startIndex, i);
			path.add(array[startIndex]);
			backtracking2(path, startIndex + 1, array, results);
			path.remove(path.size() - 1);
			swap(array, startIndex, i);
		}
	}

	private void swap(int[] num, int i, int j) {
		int temp = num[i];
		num[i] = num[j];
		num[j] = temp;
	}
	
}
